package codeTop;

public class q200 {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visit = new boolean[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]&&grid[i][j] == '1'){
                    func(i,j,grid,visit,m,n);
                    res++;
                }
            }
        }
        return res;
    }
    void func(int i,int j,char[][] grid,boolean[][] visit,int m ,int n){
        visit[i][j] = true;
        //上
        if (i>0&&grid[i-1][j]=='1'&&!visit[i-1][j]){
            func(i-1,j,grid,visit,m,n);
        }
        //下
        if (i<m-1&&grid[i+1][j]=='1'&&!visit[i+1][j]){
            func(i+1,j,grid,visit,m,n);
        }
        //左
        if (j>0&&grid[i][j-1]=='1'&&!visit[i][j-1]){
            func(i,j-1,grid,visit,m,n);
        }
        //右
        if (j<n-1&&grid[i][j+1]=='1'&&!visit[i][j+1]){
            func(i,j+1,grid,visit,m,n);
        }
    }
}
